给定一个 N 叉树,找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如,给定一个 3
叉树 :
我们应返回其最大深度,3
。
说明:
- 树的深度不会超过
1000
。 - 树的节点总不会超过
5000
。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree
自顶向下遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def __init__(self):
self.ans = 0
def maxDepth(self, root: 'Node') -> int:
self.helper(root, 0)
return self.ans
def helper(self, root, depth):
if not root:
return
if not root.children:
# 当前节点为叶子节点
self.ans = max(self.ans, depth+1)
for node in root.children:
self.helper(node, depth+1)
自底向上遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
if not root:
return 0
if not root.children:
return 1
l = []
for node in root.children:
l.append(self.maxDepth(node))
return max(l) + 1